/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
    int theHeightOfTree(TreeNode* pRoot) {
        int height = 0;
        if (pRoot == nullptr) return 0;
        else height++;
        int left_height = theHeightOfTree(pRoot->left);
        int right_height = theHeightOfTree(pRoot->right);
        height = max(left_height, right_height)+1;
        return height;
    }

  public:

    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (pRoot == nullptr) return true;
       else {
        int left_h=theHeightOfTree(pRoot->left);
        int right_h=theHeightOfTree(pRoot->right);
        if(abs(left_h-right_h)>1) return false;
        //else return true;
       }
        bool left = IsBalanced_Solution(pRoot->left);
        bool right = IsBalanced_Solution(pRoot->right);

        return left && right;
    }
};


//解法2
int dfs(TreeNode* root){
    if(root==nullptr) return 0;
    int left = dfs(root->left);
    if(left == -1) return -1; // 左子树不平衡
    int right = dfs(root->right);
    if(right == -1) return -1; // 右子树不平衡
    if(abs(left-right)>1) return -1; // 左右子树平衡，但自身不平衡
    return 1+max(left,right); // 左右子树均为平衡树，返回自身树高
}
bool Solution::IsBalanced_Solution(TreeNode* pRoot)
{
    return dfs(pRoot) != -1;
}
